package dfs;

import java.awt.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class Demo5 {
int tmp=0;
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1==null){
    return l2;
}
if(l2==null){
    return l1;
}

tmp+=(l1.val+l2.val);
l1.val=tmp%10;
tmp-=l1.val;
l1.next=addTwoNumbers(l1.next,l2.next);
return l1;
    }


    public void merge(int[] nums1, int m, int[] nums2, int n) {
       nums1= Arrays.copyOfRange(nums2,0,nums2.length);
       Arrays.sort(nums1);
    }

    public int removeDuplicates1(int[] nums) {
        HashSet<Integer>hash=new HashSet<>();
        int prv=0;
        int cur=0;
        while(cur<nums.length){
            if(!hash.contains(nums[cur])){
                nums[prv++]=nums[cur];
                hash.add(nums[cur]);
            }
            cur++;
        }
        return prv;
    }

    public int removeDuplicates(int[] nums) {
        HashMap<Integer,Integer>hash=new HashMap<>();
        int prv=0;
        int cur=0;
        while(cur<nums.length){
            if(hash.getOrDefault(nums[cur],0)>=2){
                hash.put(nums[cur],hash.get(nums[cur])-1);
            }else {
                nums[prv++]=nums[cur];
                hash.put(nums[cur],hash.getOrDefault(nums[cur],0)+1);
            }
            cur++;
        }
        return prv;
    }


    public static int maxProfit(int[] prices) {
        int []f=new int[prices.length];
        int []g=new int[prices.length];
        f[0]=-prices[0];
        g[0]=0;
        int i=1;
        while(i<prices.length){
            f[i]=Math.max(f[i-1],g[i-1]-prices[i]);
            g[i]=Math.max(g[i-1],f[i-1]+prices[i]);
            i++;
        }
        return g[i-1];
    }


    public static void main(String[] args) {
        int []num={7,1,5,3,6,4};
        System.out.println(maxProfit(num));
    }

}
